# 动态规划-零钱兑换


class Solution:

    # 动态规划相当于复用之前的代码
    def coinChange(self, coins, amount):
        dp_min = [float("inf")] * (amount+1)
        dp_min[0] = 0
        if len(coins) == 1 and amount % coins[0] != 0:
            return -1
        
        for j in coins:
            for i in range(j, amount+1):
                dp_min[i] = min(dp_min[i], dp_min[i-j] + 1)

        return dp_min[amount] if dp_min[amount] != float("inf") else -1



if __name__ == "__main__":

    c = [1,2,5]
    # c.reverse()
    # print(c)
    a = 100
    sol = Solution()
    res = sol.coinChange(c, a)
    print(res)
